10127. Единицы

Имеется целое число n, которое не делится ни на 2, ни на 5. Существуют числа, которые состоят только из единиц и делятся на n. Найти количество единиц в наименьшем таком числе.

Вход. Каждая строка содержит целое значение n (0 £ n £ 10000).

Выход. Для каждого входного значения n вывести количество единиц в наименьшем числе, состоящем из единиц и делящемся на n.

Пример входа

3

7

9901

Пример выхода

3

6

12

РЕШЕНИЕ

элементарные вычисления

Анализ алгоритма

Построим последовательность чисел a₁ = 1, a_i = (10*a_i-1 + 1) mod 10. a_i содержит остаток от деления числа, состоящего из i единиц, на n. Как только для некоторого i значение a_i станет равным 0, останавливаем итерационный процесс. Число, состоящее из i единиц, делится нацело на n.

Пример

Для числа n = 3 наименьшим числом, состоящим из одних единиц и которое делится на 3, будет 111. Для n = 7 таким числом будет 111111.

Реализация алгоритма

Читаем в цикле значение n до конца входных данных. В переменной one вычисляем значения a₁ = 1, a_i = (10*a_i-1 + 1) mod 10, пока a_i не станет равным нулю. Количество итераций count_ones в цикле равно числу единиц в искомом числе.

for(;scanf("%d",&n) == 1;)

{

for(one = 1, count_ones = 1; one > 0; count_ones++)

one = (10 * one + 1) % n;

printf("%d\n",count_ones);

}